// 堆也叫优先队列
class Heap {
  constructor(compare) {
    this.arr = []
    this.compare = compare ? compare : (a, b) => a > b
  }
  get size() {
    return this.arr.length
  }
  // 插入元素
  push(num) {
    this.arr.push(num)
    this.siftUp(this.arr.length - 1)
  }
  // 向上调整
  siftUp(inx) {
    let { arr, compare, parent } = this
    while (inx > 0 && compare(arr[inx], arr[parent(inx)])) {
      this.swap(inx, parent(inx))
      inx = parent(inx)
    }
  }
  //获得堆顶元素
  pop() {
    if(this.arr.length === 0) return null
    this.swap(0, this.arr.length - 1)
    let n = this.arr.pop()
    this.siftDown(0)
    return n
  }
  // 向下调整
  siftDown(inx) {
    let {arr, compare} = this
    while(true) {
      let tempInx = inx
      let len = arr.length
      if(2 * inx + 1 < len && compare(arr[2 * inx + 1], arr[inx])) {
        tempInx = 2 * inx + 1
      }
      if(2 * inx + 2 < len && compare(arr[2 * inx + 2], arr[tempInx])) {
        tempInx = 2 * inx + 2
      }
      if(tempInx === inx) break
      this.swap(tempInx, inx)
      inx = tempInx
    }
  }
  parent(inx) {
    return Math.ceil(inx / 2) - 1
  }
  swap(inx1, inx2) {
    let temp = this.arr[inx1]
    this.arr[inx1] = this.arr[inx2]
    this.arr[inx2] = temp
  }
}